/*
 * @Descripttion:
 * @version:
 * @Author: xiaozilai
 * @Date: 2022-11-05 10:15:23
 * @LastEditors: xiaozilai
 * @LastEditTime: 2022-11-05 14:38:21
 */
/*
 * @lc app=leetcode.cn id=1106 lang=cpp
 *
 * [1106] 解析布尔表达式
 *
 * https://leetcode.cn/problems/parsing-a-boolean-expression/description/
 *
 * algorithms
 * Hard (58.78%)
 * Likes:    99
 * Dislikes: 0
 * Total Accepted:    8.9K
 * Total Submissions: 14K
 * Testcase Example:  '"&(|(f))"'
 *
 * 给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。
 *
 * 有效的表达式需遵循以下约定：
 *
 *
 * "t"，运算结果为 True
 * "f"，运算结果为 False
 * "!(expr)"，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
 * "&(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 与的运算（AND）
 * "|(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 或的运算（OR）
 *
 *
 *
 *
 * 示例 1：
 *
 * 输入：expression = "!(f)"
 * 输出：true
 *
 *
 * 示例 2：
 *
 * 输入：expression = "|(f,t)"
 * 输出：true
 *
 *
 * 示例 3：
 *
 * 输入：expression = "&(t,f)"
 * 输出：false
 *
 *
 * 示例 4：
 *
 * 输入：expression = "|(&(t,f,t),!(t))"
 * 输出：false
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= expression.length <= 20000
 * expression[i] 由 {'(', ')', '&', '|', '!', 't', 'f', ','} 中的字符组成。
 * expression 是以上述形式给出的有效表达式，表示一个布尔值。
 *
 *
 */

// @lc code=start
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
    bool parseBoolExpr(string expression) {
        int length = expression.length();
        stack<char> ops;
        stack<char> nums;
        int index = 0;
        while (index < length) {
            switch (expression[index]) {
            case '(':
                nums.push('(');
                break;
            case 't':
                nums.push('t');
                break;
            case 'f':
                nums.push('f');
                break;
            case ')':
                helper(ops, nums);
                break;
            case ',':
                break;
            default:
                ops.push(expression[index]);
            }
            ++index;
        }
        return nums.top() == 't' ? true : false;
    }

    void helper(stack<char> &ops, stack<char> &nums) {
        char cur_operator = ops.top();
        ops.pop();
        switch (cur_operator) {
        case '!':
            handler_nor(nums);
            break;
        case '&':
            handler_and(nums);
            break;
        case '|':
            handler_or(nums);
            break;
        }
    }

    void handler_nor(stack<char> &nums) {
        char temp = nums.top();
        nums.pop();
        nums.pop();
        nums.push(temp == 't' ? 'f' : 't');
    }

    void handler_and(stack<char> &nums) {
        bool ret = true;
        while (nums.top() != '(') {
            if (ret && nums.top() == 'f') {
                ret = false;
            }
            nums.pop();
        }
        nums.pop();
        nums.push(ret ? 't' : 'f');
    }

    void handler_or(stack<char> &nums) {
        bool ret = false;
        while (nums.top() != '(') {
            if (!ret && nums.top() == 't') {
                ret = true;
            }
            nums.pop();
        }
        nums.pop();
        nums.push(ret ? 't' : 'f');
    }
};
// @lc code=end
